1. Field of the Invention
The present invention relates generally to digital computer systems, and more particularly to management of cache memory in a data storage system.
2. Background Art
Cache memory is used in data storage systems so that under typical conditions, a relatively large and slow main memory can be accessed at a relatively high rate. The cache memory is a relatively small high-speed memory that can store at any given time a portion of the data stored in the main memory. The data storage system also includes a cache directory or index of the data elements. The cache directory is referenced to provide an indication of whether or not each data element is located in the cache memory at any given time, and if so, the present location of the data element in the cache memory.
A data storage system is typically responsive to data access requests from a host computer. The data access requests, for example, include read and write requests. When a data storage system having a cache memory receives a request for access to data, the cache directory is inspected to determine whether the data element to be accessed resides in the cache memory. If so, the data storage system accesses the data in the cache memory. If not, the data storage system accesses the data in the main memory, and if the accessed data is likely to be accessed again in the near future, the accessed data is copied or "staged" into the cache memory.
In some data storage systems, data elements to be accessed are always staged into the cache memory if they are absent from the cache memory. Some data storage systems are also responsive to explicit "prefetch" commands from the host computer to cause specified data to be staged into the cache, even though the specified data is not immediately accessed by the host computer.
Because the cache memory has a capacity that is smaller than the main memory, it is sometimes necessary for data elements in the cache memory to be replaced or removed from the cache memory in order to provide space in the cache memory for receiving data elements to be staged into the cache memory. In general, for the cache memory to be useful, the data elements replaced or removed from the cache memory must be less likely to be accessed in the near future than the data elements that are staged into the cache memory.
Data storage systems that use disc drives for the main memory typically use random access memory (RAM) for the cache memory. In such a data storage system, the data elements in the cache memory are often logical tracks of data on the discs, although in many systems, the data elements are blocks or records of data. Each data element can be stored in any one of a multiplicity of blocks or slots in the cache memory. The cache directory includes a directory entry for at least each data element stored in the cache. Each directory entry for each data element stored in the cache memory includes a pointer to the location of the data element in the cache memory. The cache directory can be a table including an entry for each data element stored in the disc storage. Alternatively, the directory may include a hash table for accessing lists of the directory entries so that the cache directory need not include any cache directory entries for data elements that are absent from the cache memory. In either case, any one of a plurality of data elements in the cache memory can be replaced or removed from cache to make room for another data element to be staged into the cache memory. The performance of such a data storage system is highly dependent on the cache management strategy used for selecting the data element to be or removed or replaced. This strategy is implemented by a cache management system, or "cache manager," in the data storage system.
Typically the cache manager will remove or replace the "least-recently-used" data element in the cache memory. The "least-recently-used" data element is the usually the oldest data element accessed by a host computer. So that the cache manager can readily identify the least-recently-used data element, the cache manager maintains a list or queue of the data elements in the cache memory. The queue is typically implemented as a doubly-linked list. "Forward" and "backward" pointers for this doubly-linked list, for example, are in the cache directory entries, or in the blocks or slots in the cache. When a data element is accessed, the data element is moved to the tail of the queue unless the data element is already at the tail of the queue. If the data element is already in the cache but it is not already at the tail of the queue, it is removed from the queue before being inserted at the tail of the queue. In this fashion, so long as the queue is not empty, the least-recently-used data element in the cache memory will be at the head of the queue, and the most-recently-used data element in the cache memory will be at the tail of the queue.
Various techniques have been described for dynamically monitoring and adjusting cache management parameters. For example, Yanai et al. U.S. Pat. No. 5,381,539, issued Jan. 10, 1995, incorporated herein by reference, describes a data storage system having a cache controlled by parameters including: (a) a minimum number of data storage elements which must be retrieved and stored in cache memory and used by the system before the cache manager recognizes a sequential data access in progress; (b) a maximum number of data elements which the cache manager is to prefetch ahead; and (c) a maximum number of sequential data elements to be stored in cache before the cache memory locations containing the prefetched data elements are reused or recycled. The cache manager scans or monitors the cache directory and uses the sequential access threshold (a) and time stamps associated with the data elements in the cache to recognize the occurrence of a sequential data access in progress by a given process executing on a host computer. Once a sequential access is recognized, the cache manager prefetches ahead up to the maximum number (b) of sequential data elements. The prefetched sequential data elements are stored in the cache memory loop, but they are further identified as forming a micro-cache which is reused by the sequential process, and which has the maximum number (c) of sequential data elements to be stored in cache before the cache memory locations containing the prefetched data elements are reused or recycled. The re-using of the cache memory locations in the micro-cache prevents the sequential process from flushing data elements from other processes from the cache memory loop. The cache manager continues to monitor data use by the sequential process, and when the end of a sequential data access by the process is detected by non-use of a data element stored in the micro-cache, the cache manager will no longer re-use the cache memory locations of the micro-cache for the process, and will de-allocate any resources used for managing the micro-cache. The cache manager also dynamically adjusts the sequential access detection threshold (a) and the maximum number of data elements to prefetch (b). The cache directory includes, for each data element, a flag or bit that is reset when the data element is fetched from storage and staged into the cache, and that is set when the data element is accessed by the host. The cache manager monitors this flag to detect data elements that are prefetched but not used as anticipated by each process. When the cache manager detects many data elements that are prefetched but not used, the cache manager increases the sequential access detection threshold (a). Moreover, when the cache manager detects a large number or long continuous string of used data elements, the cache manager decreases the sequential access detection threshold (a). In this fashion, the sequential detection threshold "floats" at an optimum level for each process. The cache manager also monitors and dynamically adjusts the number of data elements to be prefetched (b) as a function of the number of sequential data elements which have been accessed by a host. Further, the cache manager dynamically adjusts the size of the micro-cache (c) for each process in response to a corresponding increase or decrease in the number of data elements to be prefetched (b) for the process.
As described above, many alternatives exist for cache managers. What is desired in a cache manager that provides the most likely data elements and which can be modified with a minimum amount of cache activity.